function BuildDT(
All_Examples, Attributes ): Decision_Tree.
LearnDT(
Training_Examples, Attributes, Default ).
PruneDT(
Testing_Examples,
RootOf( Decision_Tree
)
).
function LearnDT(
Training_Examples, Attributes, Default ):
Decision_Tree.
if
IsEmptySet( Training_Examples
) then
return
leaf( Default
).
if
AllSameClass( Training_Examples
) then
return leaf(
ClassOf( Examples[1] ) ).
if
IsEmptySet( Attributes
) then
return leaf(
MajorityValue( Training_Examples
) ).
bestAttr <-
ChooseAttribute(
Training_Examples, Attributes,
).
node <- new node( bestAttr ).
for each value
v_i of bestAttr
do.
Training_Examples_i <-
{elements of Training_Examples with
bestAttr == v_i}.
subtree <-
LearnDT(
Training_Examples_i, Attributes - bestAttr,
MajorityValue(
Training_Examples ) ).
add branch: node --- v_i -->
subtree.
end for.
return node.
end.
function
PruneReducedErrorDT(
Testing_Examples, Root_Node ): Decision_Tree.
if
IsLeaf( Root_Node
) then return
Root_Node.
current_err <- 0.
for each child
N_i of Root_Node
do.
Testing_Examples_i <-
{elements of Testing_Examples
that reach N_i}.
current_err <- current_err +
Error(
PruneReducedErrorDT(
Testing_Examples_i, N_i
), Testing_Examples
).
end for.
prune_err <-
Error( LeafWithBestTargetVal( Root_Node
), Testing_Examples
).
if
prune_err < current_err
then
return
leaf( BestTargetValue( Root_Node
), Testing_Examples
).
end.
function
PrunePessimisticDT(
Testing_Examples, Root_Node ): Decision_Tree.
if
IsLeaf( Root_Node
) then return
Root_Node.
current_err <- 0.
for each child
N_i of Root_Node
do.
Testing_Examples_i <-
{elements of Testing_Examples
that reach N_i}.
current_err <- current_err +
ErrorPPP(
PrunePessimisticDT(
Testing_Examples_i, N_i
), Testing_Examples
).
end for.
prune_err <-
ErrorPPP( LeafWithBestTargetVal( Root_Node
), Testing_Examples
).
if
prune_err < current_err
then
return
leaf( BestTargetValue( Root_Node
), Testing_Examples
).
end.